\section{Verifiable random functions}
%\subsection{Verifiable random functions}
\label{sec:VRFs}

% ...
% \subsection{...}

A {\em verifiable random function (VRF)} is a cryptographic function that generates a pseudo-random output number from a given a secret key $\skvrf$ and an input string $\alpha$ called a seed, and produces a proof of correctness for the output.  Anyone with the input and the corresponding public key $\pkvrf$ can verify the correctness of the VRF output, but only the secret key holder could compute this output.  In a sence, VRFs resemble a public-key analog of a cryptographic hash function with a distinguished key, such as MACs that acts as PRFs, in that a keyed hash function requires the key be shared for verification. 

All known elliptic curve VRFs compute some point $\gamma = \skvrf * H_1(\alpha)$ where $H_1$ hashes to the curve, and provides some correctness proof.  We cannot claim $\gamma$ is pseudo-random because elliptic curve points are not strings and these outputs are related.  Instead, we always follow the 2Hash-DH construction from Theorem 2 on page 32 in appendix C of \cite{Praos} which treats $\gamma$ as a key for an actual PRF $\omega = H(\mathtt{ctx} || h \gamma || \alpha)$ where $h$ is the cofactor.  

In more details, we formalize VRFs with following four probabilistic algorithms: 
\begin{itemize}
\item $\VRF.\KeyGen$ is a probabilistic algorithm that returns a public-secret key pair $(\pkvrf,\skvrf)$, sometimes with a security parameter $\lambda$ input.
\item $\VRF.\Sign_{\skvrf}$ is a probabilistic algorithm that takes a secret key $\skvrf$, and series of input seeds $(\alpha_1,\ldots,\alpha_n)$ for any $n\ge1$, and an extra message $m$, and yields a signature or proof $\pi$. 
\item $\VRF.\Out$ extracts our outputs $(\omega_1,\ldots,\omega_n)$ from the signature $\pi$ and the input seeds $(\alpha_1,\ldots,\alpha_n)$, with each $\omega_i$ being determined only by $\alpha_i$ and $\pkvrf$.
\item $\VRF.\Verify_{\pkvrf}$ is a probabilistic algorithm that takes a public key $\pkvrf$, a series of inputs $(\alpha_1,\ldots,\alpha_n)$, an extra message $m$, and a proof $\pi$, and outputs true or false.
\end{itemize}

We shall neglect the separate $\VRF.\Out$ routine and write $(\omega,\pi) = \VRF.\Sign_{\skvrf}(\alpha,m)$ for notational convenience.  We warn however that real $\VRF.\Sign_{\skvrf}$ routines return a tuple $(\gamma,\pi')$, and that $\VRF.\Verify_{\pkvrf}$ takes the same tuple $\pi = (\gamma,\pi')$, but this $\gamma$ requires post-processing both to remove the cofactor and for the 2Hash-DH construction that gives us a PRF.

We take $n=1$ below for convenience since one turns a VRF with $n=1$ into a VRF with $n>1$ using 
\cite[\S3.2.1]{PrivacyPass} (see Theorem 3.17 on page 74 of Ryan Henry's PhD thesis \cite{RyanHenryPhD} or \cite{HenryGoldberg13}), but doing so uses $\pkvrf$ one extra time in verification.  
We could bind the extra message $m$ into the VRF signature by increasing $n$ and ignoring its output.  Instead however, we bind $m$ directly into the proof to avoid these extra $\pkvrf$ since they increase complexity in the next section.

We impose two criteria upon our VRF that should be familiar from signature schemes, like correctness and some unforgeability notion.  As a rule, one does not always require the strongest unforgeability notions for VRFs because the output itself imposes a subtlety different criteria.  We obtain EUF-CMA however when using Schnorr DLEQ proofs. 

For any valid key pair $\pkvrf,\skvrf$, we ask:
\begin{itemize}
\item {\em Correctness:}
If $\pi = \VRF.\Sign_{\skvrf}(\alpha,m)$ then $\VRF.\Verify_{\pkvrf}(\alpha,m,\pi)$ holds.
\item {\rm Unforgeability (EUF-CMA):} 
An adversary with only knowledge of $\pkvrf$, not $\skvrf$, and who adaptively queries VRF signatures on their own chosen messages, has negligible chances to produce a $\pi$ that verifies for some $(\alpha_1,\ldots,\alpha_n)$ and $m$ in which some $\alpha_i$ or $m$ was never queried.
\end{itemize}
% TODO: What unforgeability does the SNARK give? 

Any valid key pair $\pkvrf,\skvrf$, there is a map $f_{\pkvrf}(\alpha) = \VRF.\Out(\VRF.\Sign_{\skvrf}(\alpha))$ upon which we impose additional PRF criteria.  We need $\gamma_i = f_{\pkvrf}(\alpha_i)$ in the above notation, so $\omega_i$ depends only upon $\skvrf$ and $\alpha$, not $i$.
\begin{itemize}
\item {\em Uniqueness}
An adversary with full knowledge of $\skvrf$ has negligible chances to produce a proof $\pi$ for which some $\VRF.\Verify_{\pkvrf}(\alpha,m,\pi)$ passess for the $\pkvrf$ associated to $\skvrf$, but $\VRF.\Out(\pi) \ne f_{\skvrf}(\alpha)$.
\item {\em Unpredictability}
An adversary with only knowledge of $\pkvrf$, not $\skvrf$, has negligible chances to guess the $f_{\pkvrf}(\alpha)$ corresponding to any inout seed $\alpha$.
\item {\em Pseduo-randomness}
Our family $\{ f_{\pkvrf} \}_{\skvrf}$ is a PRF, meaning an adversary that queries an oracle for either a function sampled from either $\{ f_{\pkvrf} \}_{\skvrf}$, or else a truly random function with the same domain and range, has only negligible odds to identify which kind of oracle from which she queries.
\end{itemize}
We always ensure this PRF assumption using the 2Hash-DH construction from Theorem 2 on page 32 in appendix C of \cite{Praos} as discussed above.
% TODO: Should we rearange to discusse 2Hash-DH here?
% We only require the PRF assumption because our PRF adversary always possesses $\skvrf$ in practice.  
In principle, one might explore weaker public-key pseduo-randomness assumptions, in which an adversary is given either oracle access to $\VRF.\Verify_{\pkvrf}$, etc., or else a model of these methods built from a truly random function, but any useful such definition appears identical to our PRF assumption in practice.
% TODO: Is this correct Handan?  Is this just equivelent?  If so, citation?  2Hash-DH resut?

In recent years, we witnessed an explosion of protocols that exploit related keys ${\pkvrf}_1 = k {\pkvrf}_2$ with public $k$, including reasonable protocols like the Tor Onion Services v3 \cite{TorRendSpecV3}, and dangerous customs like BIP32 \cite{BIP32}.  All related keys protocols create related key attacks on our unpredictability assumption, so VRF users must include $\pkvrf$ in the input seed $\alpha$ when also using related keys protocols.  As discussed below we avoid these extra $\pkvrf$ uses for reasons discussed in the next section, instead opting to avoid related key protocols.

There exist VRFs with $\pi = (\gamma)$ aka $\pi' = \emptyset$ like BLS signatures and RSA-FDH signatures that satisfy many of our assumptions, but only some weaker unforgability notion.  In particular, our trick for increasing $n$ permits combining multiple BLS signatures, which violates EUF-CMA.  
% TODO: Are BLS signatures EUF-CMA ever anyways?

In this paper, we shall bind an additional message into a VRF signature, which inherently prevents using BLS signatures.  We do not bother identifying a weaker notion than EUF-CMA that permits this binding, but protocol that use threshold VRFs require more care here.
% We cannot prevent an adversary from providing a zero knowledge proof of verification with only partial information, but this second condition ensures that adversaries cannot trick honest verifiers by altering the presentation of VRF outputs.  

We caution against using BLS signatures as VRFs for numerous other reasons, including their incredibly poor performance, including poor batch verification performance, lack of conservative curve choices, and that non-threshold aggregation breaks uniqueness and creates the above vulnerability to related key attacks.


\subsection{Ring VRFs}
\label{sec:ringVRF}

A ring VRF operates like a VRF but only proves its key comes from a specific list without giving any information about which specific key.  Any ring VRF yields sortition:

In a pre-announce phase, all block producers anonymously publish ring VRF outputs, which either requires revealing their identity to another block producer, or else requires a multi-hop anonymity network.  We then sort these ring VRF outputs and block producers claim them when making blocks.

We now formalize ring signatures and VRFs with first a commitment scheme for public keys:
\begin{itemize}
\item $\algo{Commit}(\pk_1,\ldots)$ returns a commitment $\pkc$ and an openning $\skc_i$ for each public key $\pk_i$ in the supplied public key set,
\end{itemize}
as well as adopting our normal methods to operate on commitments:
\begin{itemize}
\item $\Sign_{\sk,\skc}$ now requires the openning of the commitment to the public key set, as well as the secret key.
\item $\Verify_{\pkc}$ now takes a commitment to the public key set, instead of a public key.
\end{itemize}
In practice, ring VRFs always possess the original non-ring VRF $\Sign_{\skvrf}$ and $\Verify_{\pkvrf}$ methods too.  

We shall not hide the input seeds $\alpha$, which avoids hashing-to-the-curve in zero-knowledge, but prevents including $\pkvrf$ in $\alpha$, and requires avoiding related key protocols.

All $\Sign$ methods compute their outputs $\omega$ well before computing their proofs $\pi$, with $\omega$ along being roughly twice as fast for normal VRFs, and many thousands of times faster for ring VRFs.  Almost all VRF protocols throw away many VRF outputs, so VRFs always include methods that test the outputs with some closure before computing the proofs.

There are naive ring VRF constructions with signature size linear in the number of signers, which appear unacceptable for our use case.  Indeed, these scale worse than well optimised accountable shuffle operations discussed in the appendix.

\paragraph{Instantiation with zkSNARKs:}

We instead favour constant-size ring VRFs built using zkSNARKs, which should support 10k signers with only about 10k to 20k constraints.  TODO: Do you agree Sergey?
% TODO: link https://ethresear.ch/t/cryptographic-sortition-possible-solution-with-zk-snark/5102 anywhere?

TODO:  Discuss https://github.com/w3f/ring-vrf/

TODO:  Groth16 \cite{Groth16}, subversion resistance, Posidon etc.

There are also ring signature constructions that do not require pairings and require only logarithmic size.  As an older example, ring signatures \cite{GK2015} need about 32*7 bytes times the logarithm of the number of validators, so under 3kb for 10,000 validators.  We also note that ring VRFs are linkable ring signatures, so some existing linkable ring signatures implementations may already provide ring VRFs.

\paragraph{Instantiation with Inner product arguments:}

We shall strongly consider the inner product proofs of Bootle, et al. \cite{bccgp2016}.  In this, the signer/prover commits to a secret vector $\bar{v}$ of positive numbers, proves that $\bar{v}_i = H_1(\mathsf{input})$ for exactly one $i$ and that $\bar{v}_j = 0$ for all $j \ne i$, and that the inner product of $\bar{v}$ with the block producer public keys equals the VRF output.  TODO:  Is this really this simple?  Not likely

In practice, we consider the dalek implementation \cite{dalek_bulletproofs} of \cite{bulletproofs}, which itself consists of \cite{bccgp2016} plus multi-proving and batching techniques.
% [dalek bulletproofs crate](https://doc-internal.dalek.rs/bulletproofs/notes/index.html)

At our number of block producers, we expect the non-pairing based technique to prove fairly competitive sizes with zkSNARKs, but verification still requires linear computation time.  At 10k validators, zkSNARK would costs the prover like 10k-20k scalar multiplications, but provide faster verification, while the non-pairing based scheme might cost verifiers 10k scalar multiplications per slot.  

There exist better batching techniques for inner product proofs \cite{bccgp2016} in the bulletproofs approach \cite{bulletproofs} than exist for \cite{Groth16}.  We might yet find that zkSNARKs remain more efficient, especially if we cannot apply the multi-proving tools of \cite{bulletproofs}.


\subsection{Group VRFs}
\label{sec:groupVRF}

A group signature also hides the specific signer, like a ring signature, but group signatures require initial setup via some issuer or MPC. 

We could build a group VRF similarly to a group signature by using the rerandomizable signature scheme from \cite{PS16} as a blind rerandomizable certificate.  Our issuer would first blind sign each validator's private key, like in \S6.1 of \cite{PS16}, so that later each validator can prove correctness their VRF output, replacing the proof of knowledge from \S6.2 of \cite{PS16}.  We believe this final step resembles the Schnorr DLEQ proof based VRF except with the public key replaced by the signature inputs, but run on the pairing based curve.

In this, we must take care with our pairing assumptions because we loose anonymity if $x H$ with $H$ known ever appears on the curve not used for the VRF output.  

It appears group VRFs only require a few curve points, and verification only requires two pairings and a few scalar multiplications, making them far smaller and faster than ring VRFs.  We require a distributed issuer however, which dramatically complicates the protocol:

We'd want at least two thirds, but preferable all, of validators to be aggregate certificate issuers, meaning they have certified the blinded public keys of all validators and we aggregate all certificates and public keys.  We might achieve this with an MPC but doing so requires choosing {\em when} issuers issue certificates;   

We become therefore tempted to run this MPC after election but before establishing final validator list, but this complicates protocol layering.  Instead, we could ask that all new prospective validators certify all previously added prospective validators, and all previously added prospective validators eventually recertify all more recently added prospective validators.  In this second approach, any spammed slots in \S\ref{sec:preannounced} ?? originate from prospective but not actual validators, probably along with an actual validator who posts them.  

We could look into group signatures with ``verifier local revocation'' but these get much more complicated.

% \subsection{...}



